package com.lyb.sort;

import java.util.Arrays;

/**
 * 归并排序
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] nums = {8,3,-9,1,0,4,7,2,5,6};
        sort(nums,0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }

    public static void sort(int[] nums,int start, int end){
        if (start >= end){
            return;
        }
        //取中间数
        int mid = (start + end) / 2;
        //对左边一半排序
        sort(nums,start, mid);
        //对右边一半排序
        sort(nums,mid + 1 ,end);
        //合并
        merge(nums,start,mid,end);
    }

    private static void merge(int[] nums, int start, int mid, int end) {
        //创建一个临时数组
        int[] result = new int[end - start + 1];
        int i = start; //第一部分的起点
        int j = mid + 1; //第二部分的起点
        int k = 0; //临时数组的索引

        //从两个部分的起点开始比较，直到一个部分到达终点
        while (i <= mid && j <= end){
            if (nums[i] < nums[j]){
                result[k++] = nums[i++];
            }else {
                result[k++] = nums[j++];
            }
        }

        //将两部分剩余的元素放到临时数组
        while (i <= mid){
            result[k++] = nums[i++];
        }

        while (j <= end){
            result[k++] = nums[j++];
        }

        //将临时数组的内容拷贝到原数组指定区间
        System.arraycopy(result,0,nums,start,result.length);
    }
}
